package leetcode.top100;

/**
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 * <p>
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * <p>
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * <p>
 * 示例 1:
 * <p>
 * nums1 = [1, 3]
 * nums2 = [2]
 * <p>
 * 则中位数是 2.0
 * 示例 2:
 * <p>
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * <p>
 * 则中位数是 (2 + 3)/2 = 2.5
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @date 2020/3/23 16:00
 */
public class Code04_FindMedianInSortedArr {

    /**
     * 方式1：时间O(m+n),空间O(m+n)，外排
     *
     * 奇数下：len-1/2 == len/2为中间那个
     * 偶数下：len-1 /2是中间靠前，len/2是中间靠后。
     */

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        Double x = doubleCheck(nums1,nums2);
        if(x != null) return x;
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len = len1 + len2;
        int a[] = new int[len];
        int p1 = 0;
        int p2 = 0;
        int index = 0;
        while (p1 < len1 && p2 < len2) {
            a[index++] = nums1[p1] < nums2[p2] ? nums1[p1++] : nums2[p2++];
        }
        while (p1 < len1) a[index++] = nums1[p1++];
        while (p2 < len2) a[index++] = nums2[p2++];
        return (len & 1) == 0 ? (a[(len-1)/2] + a[len/2])/2.0 : a[len/2];
    }

    /**
     * 方式2：也是基于快排，但是不需要真正地排，只需要做标记。
     *
     */
    public static double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        Double x = doubleCheck(nums1,nums2);
        if(x != null) return x;
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len = len1 + len2;
        //总索引数，从0开始计算，当到达(len1+len2)/2时，就是after。
        int aimIndex = -1;
        int before = Math.min(nums1[0],nums2[0]);//记录len-1/2处元素
        int after = before;//记录len/2处元素
        int p1 = 0;
        int p2 = 0;
        while (p1 < len1 && p2 < len2){
            //把before更新为after，因为after要从新更新了
            after = nums1[p1] < nums2[p2] ? nums1[p1++] : nums2[p2++];
            if(++aimIndex == len / 2){
                return (len & 1) == 0? (after + before) / 2.0 :
                        after;
            }
            before = after;

        }
        while (p1 < len1){
            after = nums1[p1++];
            if(++aimIndex == len/ 2){
                return (len & 1) == 0? (after + before) / 2.0 :
                        after;
            }
            before = after;
        }
        while (p2 < len2){
            after = nums2[p2++];
            if(++aimIndex == len / 2){
                return (len & 1) == 0? (after + before) / 2.0 :
                        after;
            }
            before = after;
        }

        return -1;

    }

    /**
     * 方式3：二分法。对两个数组找中位数。假设总长度len为奇数，就是找第len/2位置的数，
     * 换言之就是找第 k = len/2+1小的数。
     * 所以直接比较num1与num2中各自 k/2位置的数。如果num1的小于num2的，那么num1的0-k/2都比num2[k/2]小，
     * 所以排除掉k/2个。剩余len - k/2个数中，找第k-k/2小的数，在此基础上递归上述过程。
     */
    public static double findMedianSortedArrays2(int[] nums1, int[] nums2){
        Double x = doubleCheck(nums1,nums2);
        if(x != null) return x;
        int len = nums1.length + nums2.length;
        //奇数，找len/2处，也就是第len/2+1小的数
        if((len & 1) != 0) {
            return getKth(nums1,0,nums1.length-1,nums2,0,nums2.length-1,len/2+1);
        }
        //偶数,找len-1/2处和len/2处，
        return (getKth(nums1,0,nums1.length-1,nums2,0,nums2.length-1,(len-1)/2+1) +
                getKth(nums1,0,nums1.length-1,nums2,0,nums2.length-1,len/2+1))/2.0;
    }
    /**
     * 在两个数组中，找第k小的数。
     * 思路是在各自数组中找第k/2小，然后比较该位置大小，可以排除一半。
     */
    private static double getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //直接找num2中的第k小的数
        if(len1 <= 0)
            return nums2[start2 + k - 1];

        if(len2 <= 0)
            return nums1[start1 + k - 1];
        //注意这里必须要判断：因为k=1表示在数组中找最小的数。如果不判断，
        //分隔到两个数组中就是找第0小的数，非法。
        // 找第k小的数对应的索引就是 k-1，第0小索引就是-1，会造成越界！
        if(k == 1)
            return Math.min(nums1[start1],nums2[start2]);
        //如果 len1 <= k/2 ，直接定位到len1-1，否则定位到k/2
        int i = start1 + Math.min(len1,k/2) - 1;
        //如果 len2 <= k/2 ，直接定位到len2-1，否则定位到k/2
        int j = start2 + Math.min(len2,k/2) - 1;
        if(nums1[i] > nums2[j]){
            //num2从start2 - j所有的数都比num1[i]小，可以排除
            return getKth(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));
        }else {
            return getKth(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));
        }
    }

    private  static Double doubleCheck(int[] num1,int []num2){
        if(num1 == null && num2 == null || num1.length == 0 && num2.length == 0)
            throw new RuntimeException("feifa");
        //get median nums2.奇数偶数统一
        if(num1 == null || num1.length == 0)
            return (num2[(num2.length-1)/2] + num2[num2.length/2])/2.0;
        if(num2 == null || num2.length == 0)
            return  (num1[(num1.length-1)/2] + num1[num1.length/2])/2.0;
        return null;//合法
    }
    public static void main(String[] args) {
        int[] a1 = {1,3};
        int[] a2 = {2};
        System.out.println(findMedianSortedArrays2(a1, a2));
    }
}
